
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    /**
     * 第一遍 2/23
     * @param head
     * @param k
     * @return
     */
//    public ListNode reverseKGroup(ListNode head, int k) {
//        if (head == null) return null;
//
//        ListNode a = head, b = head;
//        for (int i = 0; i < k; i++) {
//            // 走到后面，发现b到底了，而还没到k: 不足k个不需要反转
//            if (b == null) return head;
//            b = b.next;
//        }
//        // 反转前k(a到b)个元素
//        ListNode newHead = reverse(a, b);
//        // 递归反转后，将后续链表连接起来
//        a.next = reverseKGroup(b, k);
//        return newHead;
//    }
//
//    /* 反转区间 [a, b) 的元素，注意是左闭右开 */
//    // 例如 1->2->3  --->   null<-1<-2->3
//    ListNode reverse(ListNode a, ListNode b) {
//        ListNode pre, cur, nxt;
//        pre = null;
//        cur = a;
//        nxt = b;
//        while (cur != b) {
//            nxt = cur.next;
//            cur.next = pre;
//            pre = cur;
//            cur = nxt;
//        }
//        return pre;
//    }

    //       1    ->    2    ->3
    // nxt = cur.next;
    // pre  cur        nxt
    // cur.next = pre
    // pre <- 1
    // pre = cur; cur = nxt;
    //      pre       nxt


    /**
     * 第二遍2/25
     * @param head
     * @param k
     * @return
     */
//    public ListNode reverseKGroup(ListNode head, int k) {
//        if (head == null) return null;
//
//        ListNode a = head, b = head;
//        for (int i = 0; i < k; i++) {
//            // k还没走完，b走完了
//            if (b == null) return head;
//            b = b.next;
//        }
//
//        // 这个时候b走到k了,反转[a-b),左闭右开
//        ListNode newHead = reverse(a, b);
//        a.next = reverseKGroup(b, k);
//        return newHead;
//    }
//
//    // 反转[a-b),左闭右开
//    ListNode reverse(ListNode a, ListNode b) {
//        ListNode pre, cur, nxt;
//        pre = null;
//        cur = a;
//        nxt = b;
//        while (cur != null && cur != b) {
//            nxt = cur.next;
//            cur.next = pre;
//            pre = cur;
//            cur = nxt;
//        }
//        return pre;
//    }


    /**
     * 第三遍 2/27
     *
     * @param head
     * @param k
     * @return
     */
//    public ListNode reverseKGroup(ListNode head, int k) {
//         if (head == null) return null;
//
//         ListNode slow = head, fast = head;
//        for (int i = 0; i < k; i++) {
//            // k还没完，fast先到头了
//            if (fast == null) return head;
//            fast = fast.next;
//        }
//
//        // 这个时候fast走到了k，反转[slow,fast）
//        ListNode newHead = reverse(slow,  fast);
//        // 把剩下的还放进主循环
//        slow.next = reverseKGroup(fast, k);
//        return newHead;
//    }
//
//    ListNode reverse(ListNode slow, ListNode fast) {
//        ListNode pre = null;
//        ListNode cur = slow;
//        ListNode nxt = fast;
//
//        while (cur != null && cur != fast) {
//            nxt = cur.next;
//            cur.next = pre;
//            pre = cur;
//            cur = nxt;
//        }
//        return pre;
//    }


    /**
     * 第四遍 3/7
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;

        // 快慢指针
        ListNode slow = head, fast = head;
        for (int i = 0; i < k; i++) {
            // 链表长度小于k
            if (fast == null) {
                return head;
            }
            fast = fast.next;
          }

        // 这是fast到达k点
        // 反转slow-fast
        ListNode newNode = reverse(slow, fast);
        slow.next = reverseKGroup(fast, k);
        return newNode;
    }

    ListNode reverse(ListNode slow, ListNode fast) {
        ListNode pre = null, cur = slow, nxt = fast;
        // 因为cur != fast ，所以反转是【slow,fast)左闭右开区间
        while (cur != null && cur != fast) {
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
